| 计蒜客 | 您所在的位置：网站首页 › 跳棋问题 没有能达到y=5 › 计蒜客 |
计蒜客
|
一维跳棋
本题思路类似八数码问题，节点之间进行交换使得节点序列满足题目要求序列。由于此题是一维的，不需要状态压缩，比八数码简单一些。 节点：当前的序列顺序str，遍历到当前节点时的空格序列step，当前序列中空格的位置（替换str.find()函数） 边界：当前顺序与要求顺序相同时break 队列节点：空格前后两格的棋子，满足条件即可入队 入队判重：使用map对过程中出现的序列进行判重 个人思路的大体方向没有错。对空格前后两格棋子进行遍历，满足范围条件，与空格，即数字0交换位置，并在入队节点的step后追加空格交换后所在位置。 提示：将B,W,空格转换为0， 1， 2 个人思路此题使用bfs有些抽象，不像迷宫哪些容易想到，不知道如何扩散。 开始思路是以空格坐标作为参数，把能到达当前空格坐标的所有点加入队列，当空格位于N+1的位置且左右两边的符号不同时，说明棋子归位了。 超时代码因为string容器，当N = 7是，运行速度过慢。先体会一下bfs的解题分析思路 #include using namespace std; int N; struct node{ string str, step; node(){} node(string str, string step = ""): str(str), step(step){} }; int main(){ scanf("%d", &N); string start, result; for(int i = 0; i start += "2"; result += "1"; } node n; queue q; set Close; q.push(node(start)); while(1){ n = q.front(); q.pop(); Close.insert(n.str); if(n.str == result) break; int l = n.str.find("0"); //遍历空格位置的前后两格的棋子 for(int i=-2; i if(cnt cout string status;//当前节点序列 vector step;//从开始到当前节点所有的空格位置 int pos0 = -1;//当前序列的空格位置 Node(){} Node(string str, int p){ status = str; pos0 = p; } }startNode, resultNode; string strswap(string s, int x, int y) { char temp = s[x]; s[x] = s[y]; s[y] = temp; return s; } int main(){ scanf("%d", &N); //初始化 string start, result; for(int i = 0; i start += "2"; result += "1"; } startNode = Node(start, N); startNode.step.push_back(N); resultNode = Node(result, N); resultNode.step.push_back(N); queue q; q.push(startNode); inq[startNode.status] = true; while(!q.empty()) { Node top = q.front(); q.pop(); if(top.pos0 == resultNode.pos0)//边界 { if(top.status == result)//输出 { int cnt = 0; for(int i = 1; i printf("%d ", top.step[i] + 1); cnt++; } else { printf("%d\n", top.step[i] + 1); cnt = 0; } } break; } } for(int i = 0; i string tstatus = strswap(top.status, top.pos0, tx); if(!inq[tstatus]) { Node temp = Node(tstatus, tx); temp.step = top.step; temp.step.push_back(tx); q.push(temp); inq[tstatus] = true; } } } } return 0; } |
【本文地址】
公司简介
联系我们